package bit;

import java.util.ArrayList;
import java.util.List;

public class leetcode89格雷编码 {
    // 镜像G(n) = A(n - 1) + B(n - 1),A(n - 1)数组中原来的数，B(n - 1)表示数组中原来的数倒序，前边加1
    public static List<Integer> grayCode(int n) {
        List<Integer> list = new ArrayList<>();
        list.add(0);
        int bit = 1;
        for (int i = 1; i <= n; i++) {
            int size = list.size();
            for (int j = size - 1; j >= 0; j--) {
                list.add(list.get(j) | bit);
            }
            bit <<= 1;
        }
        return list;
    }

    // dfs
    public List<Integer> grayCode1(int n) {
        List<Integer> list = new ArrayList<>();
        dfs(list, new StringBuilder(), new int[]{0,1}, n);
        return list;
    }

    public void dfs(List<Integer> list, StringBuilder builder, int[] bit, int n){
        if (n == 0) {
            list.add(Integer.valueOf(builder.toString(),2));
        } else {
            builder.append(bit[0]);
            dfs(list, builder, new int[]{0,1}, n - 1);
            builder.deleteCharAt(builder.length() - 1);
            builder.append(bit[1]);
            dfs(list, builder, new int[]{1,0}, n - 1);
            builder.deleteCharAt(builder.length() - 1);
        }
    }
}
